void **vmheap, **endvmheap; //active heap
void **nextfreeinheap; //next free address in the heap
int heapsize; //max size of heap
void **stackstart; //pointer to the start of the stack
void ***writepoint; //used during gc 
void ***readpoint; //used during gc



void init_gc(){
  heapsize = 1<<15;
  vmheap = nextfreeinheap = (void **) malloc(sizeof(void *) * heapsize);
  endvmheap = vmheap + heapsize;
}


/**
   Evacuate tests if an object at a given address has already been
   copied to the new heap. If so, it returns the new address of this 
   object.
   If not, evacuate copies this object to the new heap, updates the object
   in the old heap, to point to the object in the new heap and returns 
   the new address of the object
**/
void **evacuate(void **oldheapobject, void **newheap) {
  //if object has already been evacuated return pointer to new object
  if (((void *) newheap <= *oldheapobject) && (*oldheapobject < (void *) (newheap+heapsize))){
    return *oldheapobject;
  }

  // copy object pointed to from stackpoint to writepoint
  int objectsize = ((int *) *oldheapobject)[1];
  if(!objectsize) objectsize = ((int *) oldheapobject)[1] + 2;
  void **oldread = oldheapobject;//remember where we started reading
  void **addr = (void **) writepoint; //remember where we started writing

  //copy address by address
  int i;
  for (i = 0; i<objectsize; i++) {
    *writepoint =  *oldread;
    writepoint++;
    oldread++;
  }

  // change old heap object to point to the new and return
  *oldheapobject = addr;
  return addr;
}





/**
   Scavenge iterates over the new heap evacuating any objects 
   referenced in the old heap and updating the references to these 
   objects
*/
void scavenge(void **newheap){
  //scan over objects at readpoint
  while (readpoint < writepoint) {
    if ((*readpoint >= vmheap) && (*readpoint < endvmheap)) {
      *readpoint = evacuate(*readpoint, newheap);
    }
    int size = ((int *) *readpoint)[1];
    if(!size){
      size = ((int *) readpoint)[1] + 1;
      readpoint++;
    }else if((class *) *readpoint == &inttype || (class *) *readpoint == &booltype){
      size--;
      readpoint++;
    }
    size--;
    readpoint++;
    
    while(size--){
      //if pointer into oldheap found, evacuate and update
      if ((*readpoint >= vmheap) && (*readpoint < endvmheap)) {
	*readpoint = evacuate(*readpoint, newheap);
      }
      //increase readpoint
      readpoint++;
    }
  }
}






/**
   gc performs stop and copy garbage collection.
   - first a new heap space is created
   - second all 'root objects' are found from the stack and evacuated
   to the new heap
   - third the new heap is scavenged, evacuating all objects referenced
   - finally the old heap is freed and the new heap is set as active.
**/
void gcStopAndCopy() {
  //create new heap
  int x = 0xdeadbeef;
  void **newheap;
  newheap = (void **) malloc(sizeof(void *) * heapsize);
  writepoint = (void ***) newheap;
  readpoint = (void ***) newheap;
  //scan through stack
  void **stackpoint = stackstart;
  void **stackend = (void **)&x;

  while (stackpoint >= stackend) {
    //if stackpoint contains address pointing into old heap: evacuate
    if ((*stackpoint >= (void *) vmheap) && (*stackpoint < (void *) endvmheap)) {
      *stackpoint = evacuate(*stackpoint, newheap);
    }
    stackpoint--;
  }

  //search the moved objects for refs:
  scavenge(newheap);

  //free the old heap
  free(vmheap);
  vmheap = newheap;
  endvmheap = newheap + heapsize;
  nextfreeinheap = (void **) writepoint;
  return;
}








/**
   DOES NOT WORK - does not update any references to the moved objects!

   increaseheap tries to increase the max heapsize by 
   allocating double the amount of heap space, moving all content
   from old heap to the new heap and updating heapsize and the 
   nextfreeinheap index.
**
void increaseheap() {
  //create new heap
  void **newheap;
  newheap = (void **) malloc(heapsize*2);
  writepoint = (void ***) newheap;
  readpoint = (void ***) vmheap;

  //copy old heap to new heap:
  //copy address by address
  int i;
  for (i = 0; i<heapsize; i++) {
    *writepoint =  *readpoint;
    writepoint++;
    readpoint++;
  }

  //free hold heap and activate new heap  
  free(vmheap);
  heapsize = heapsize*2;
  vmheap = newheap;
  endvmheap = newheap + heapsize;
  *nextfreeinheap = *writepoint;
}
**/



/**
   //implemented in assembly in jit.c instead..

   alloc tries to allocate a given amount of space in our heap. If
   there is not enough space available alloc activates the garbage
   collector to free heap space. If this is not enough, alloc tries 
   to increase the max heap size.
   After these checks alloc designates the desired amount of space for
   the caller and returns the starting address of the heap area.
   returns ?? if the desired space could not be granted!
**/
/*
void **alloc(int allocationsize) {
  void **addr;
  //do garbage collection if not enough space is available
  if (nextfreeinheap + allocationsize > endvmheap) {
    gcStopAndCopy();
    //increase heapsize if not enough space is available after gc
    if (nextfreeinheap + allocationsize > endvmheap)
      increaseheap(); //XXX: should this take needed spaec in consideration??
  }

  //do allocation if space is available 
  if (nextfreeinheap + allocationsize <= endvmheap) {
    addr = nextfreeinheap;
    nextfreeinheap += allocationsize;
    return addr;
  } else { //gc and heapincrease was not enough...
    return addr;
  }
}
*/
